package org.example.heterogeneous;

import lombok.Data;
import org.example.util.DisJointSet;

import java.util.*;

@Data
public class TrussCommunity {

    // 输入的边
    private List<Edge> edgeList;

    // 输入的顶点
    private List<Node> nodeList;

    // 带有trussness的每条边
    private List<Edge> edgeTrussNess;

    // 邻接表
    private List<AdjacencyEdge> adjacencyEdgeList;

    // 存储边的支持度
    private Map<String, Integer> supMap;

    private int[] first;

    // 每条边存储在edgeList中的索引，例如边1-2在edgeList中的索引为1
    private Map<String, Integer> edgeIndexMapGp;

    // Gp图中的边
    private List<Edge> edgeListGp;

    // Gp图中的顶点
    private List<Node> nodeListGp;

    // Gp图中的邻接表
    private List<AdjacencyEdge> adjacencyEdgeListGp;

    // Gp图中存储边的支持度
    private Map<String, Integer> supMapGp;

    private int[] firstGp;

    private int[] degreeGp;

    // 记录Gp图中每个顶点的邻居顶点
    Map<Integer, Set<Integer>> neighborNodeGp;

    // 元路径
    private List<Integer> metaPath;

    // 元路径中中间类型顶点的P-star：其中map中的key为G图中的索引，Set中存储的为Gp图中的索引
    private Map<Integer, Set<Integer>> middleTypeNodePStar;

    // G图到Gp图的索引映射
    private Map<Integer, Integer> GToGpMap;


    public TrussCommunity(List<Edge> edgeList, List<Node> nodeList, List<AdjacencyEdge> adjacencyEdgeList, int[] first) {
        this.edgeList = edgeList;
        this.nodeList = nodeList;
        this.adjacencyEdgeList = adjacencyEdgeList;
        this.first = first;
    }

    public void basicBTruss(List<Integer> path, String q, int targetType, int k) {
        Node targetNode = null;
        // 寻找目标类型的顶点集合
        List<Node> targetNodeList = new ArrayList<>();
        for (Node node : nodeList) {
            if (node.getType() == targetType) {
                targetNodeList.add(node);
                if (targetNode == null && q.equals(node.getContent())) {
                    targetNode = node;
                }
            }
        }
        // 未找到目标顶点
        if (targetNode == null) {
            System.out.println("未找到目标顶点q=" + q);
            return;
        }

        // 创建Gp图
        creatGp(path, targetNodeList);

        Queue<Integer> tempQ = new LinkedList<>();
        int x, y;

        // 计算支持度
        String edgeKey;
        supMapGp = new HashMap<>();
        for (Edge edge : edgeListGp) {// 对于边(x,y)
            // 小的顶点在前面，大的顶点在后面
            edgeKey = Utils.getEdgeKey(edge.getU(), edge.getV());
            // 去除重边的支持度的计算
            if (supMapGp.containsKey(edgeKey)) {
                continue;
            }
            // 令x为度较小的顶点
            if (degreeGp[edge.getU()] <= degreeGp[edge.getV()]) {
                x = edge.getU();
                y = edge.getV();
            } else {
                x = edge.getV();
                y = edge.getU();
            }
            int sup = 0;
            for (int i = firstGp[x]; i != -1; i = adjacencyEdgeListGp.get(i).getNext()) {
                int z = adjacencyEdgeListGp.get(i).getV();// 得到边(x,z)
                for (int j = firstGp[y]; j != -1; j = adjacencyEdgeListGp.get(j).getNext()) {
                    if (adjacencyEdgeListGp.get(j).getV() == z) {// 若存在边(y,z),则边(x,y)的支持度加1
                        edge.increaseSup();
                        ++sup;
                    }
                }
            }
            supMapGp.put(edgeKey, sup);
            // 如果边的支持度小于k-2，则将其添加到Q中
            if (sup < (k - 2)) {
                tempQ.add(edgeIndexMapGp.get(edgeKey));
            }
        }

        // 删除支持度小于k-2的边，并更新相应的其他边的支持度
        deleteEdgeFromGpAndUpdate(tempQ, k);

        // 根据算法得到的边信息构建社区
        basicBTrussCommunitySearch(q);

    }

    public void fastBTruss(List<Integer> path, String q, int targetType, int k) {
        Node targetNode = null;
        // 寻找目标类型的顶点集合
        List<Node> targetNodeList = new ArrayList<>();
        for (Node node : nodeList) {
            if (node.getType() == targetType) {
                targetNodeList.add(node);
                if (targetNode == null && q.equals(node.getContent())) {
                    targetNode = node;
                }
            }
        }
        // 未找到目标顶点
        if (targetNode == null) {
            System.out.println("未找到目标顶点q=" + q);
            return;
        }

        // 创建Gp图
        creatGpWithPStar(path, targetNodeList);

        // nodeInCs标识Gp中的顶点是否在Cs中
        boolean[] nodeInCs = new boolean[nodeListGp.size() + 1];
        List<Set<Integer>> Cs = new ArrayList<>();
        int middleUType = path.get(path.size() / 2);

        for (Node node : nodeList) {
            if (node.getType() == middleUType) {
                Set<Integer> Su = middleTypeNodePStar.get(node.getId());
                if (Su != null) {
                    Set<Integer> SuInGp = new HashSet<>();
                    // 将set中存储的G图中的索引更新为Gp图中的索引
                    for (Integer temp : Su) {
                        Integer x = GToGpMap.get(temp);
                        if (x != null) {
                            SuInGp.add(x);
                        }
                    }
                    middleTypeNodePStar.put(node.getId(), SuInGp);
                    // Su中至少有k个顶点
                    if (SuInGp.size() >= k) {
                        Cs.add(SuInGp);
                        for (Integer temp : SuInGp) {
                            nodeInCs[temp] = true;
                        }
                    }
                }
            }
        }


        List<Integer> sortedNodeListGp = new ArrayList<>();
        for (int i = 0; i < nodeListGp.size(); ++i) {
            sortedNodeListGp.add(i);
        }
        // 将Gp中的顶点按照度的大小来升序排列（这里只排序了他们的索引）
        Collections.sort(sortedNodeListGp, new Comparator<Integer>() {
            @Override
            public int compare(Integer u, Integer v) {
                return degreeGp[u] - degreeGp[v];
            }
        });

        Queue<Integer> tempQ = new LinkedList<>();
        // 存储边是否被添加到Q中
        Map<Integer, Boolean> inQ = new HashMap<>();
        supMapGp = new HashMap<>();
        for (Integer u : sortedNodeListGp) {
            int alpha = 0;
            Set<Integer> neighbors = neighborNodeGp.get(u);
            if (neighbors != null) {
                for (Integer v : neighbors) {
                    String edgeKey = Utils.getEdgeKey(u, v);
                    if (nodeInCs[u] && nodeInCs[v]) {
                        supMapGp.put(edgeKey, Utils.INF);
                        continue;
                    }
                    // 如果顶点v的度较小，则说明边(u,v)的支持度已经计算过
                    if (degreeGp[v] < degreeGp[u]) {
                        Integer uvSup = supMapGp.get(edgeKey);
                        if (uvSup != null && uvSup < (k - 2))
                            alpha = alpha + 1;
                        continue;
                    }
                    int sup = EPSupport(u, v, k);
                    supMapGp.put(edgeKey, sup);
                    if (sup < (k - 2)) {
                        Integer index = edgeIndexMapGp.get(edgeKey);
                        if (!inQ.containsKey(index)) {
                            tempQ.add(index);
                            inQ.put(index, true);
                        }
                        alpha = alpha + 1;
                    }
                    // 如果满足条件，则说明顶点u肯定不符合条件，那就可以将带u的所有P-pairs提前删除掉
                    // 并同时更新因删除该边所影响的其他边的支持度，并将支持度小于k-2的边添加到Q中
                    if (alpha > (degreeGp[u] - k + 1)) {
                        for (Integer temp : neighbors) {
                            edgeKey = Utils.getEdgeKey(temp, u);
                            supMapGp.put(edgeKey, 0);
                            Integer index = edgeIndexMapGp.get(edgeKey);
                            if (!inQ.containsKey(index)) {
                                tempQ.add(index);
                                inQ.put(index, true);
                            }
                        }
                        break;
                    }
                }
            }
        }

        // 删除支持度小于k-2的边，并更新相应的其他边的支持度
        deleteEdgeFromGpAndUpdate(tempQ, k);

        // 根据算法得到的边信息构建社区
        basicBTrussCommunitySearch(q);
    }

    public int EPSupport(int u, int v, int k) {
        int s = 0;
        int ss = 0;
        int x, y;
        // 令x为度较小的顶点
        if (degreeGp[u] <= degreeGp[v]) {
            x = u;
            y = v;
        } else {
            x = v;
            y = u;
        }

        for (int i = firstGp[x]; i != -1; i = adjacencyEdgeListGp.get(i).getNext()) {
            int w = adjacencyEdgeListGp.get(i).getV();
            Set<Integer> y_neighbor = neighborNodeGp.get(y);
            if (y_neighbor != null) {
                if (y_neighbor.contains(w)) {
                    s += 1;
                } else {
                    ss += 1;
                }
            } else {
                ss += 1;
            }
            if (ss > (degreeGp[x] - k + 2))
                return 0;
        }
        return s;
    }

    /**
     * 删除支持度小于k-2的边，并更新相应的其他边的支持度
     *
     * @param tempQ
     * @param k
     */
    public void deleteEdgeFromGpAndUpdate(Queue<Integer> tempQ, int k) {
        int x, y;
        while (!tempQ.isEmpty()) {
            Integer e = tempQ.poll();
            Edge edge = edgeListGp.get(e);

            String xy_supKey = Utils.getEdgeKey(edge.getU(), edge.getV());
            // 若该边已经被删除了，则跳过
            if (supMapGp.get(xy_supKey) == -1) {
                continue;
            }
            // 边(x,y)的支持度为-1表示该边已经被删除了
            supMapGp.put(xy_supKey, -1);
            --degreeGp[edge.getU()];
            --degreeGp[edge.getV()];

            // 令x为度较小的顶点
            if (degreeGp[edge.getU()] <= degreeGp[edge.getV()]) {
                x = edge.getU();
                y = edge.getV();
            } else {
                x = edge.getV();
                y = edge.getU();
            }
            // 更新在同一个三角形中其它边的sup
            for (int i = firstGp[x]; i != -1; i = adjacencyEdgeListGp.get(i).getNext()) {
                int z = adjacencyEdgeListGp.get(i).getV();// 得到边(x,z)
                String xz_supKey = Utils.getEdgeKey(x, z);
                // 若该边已经被删除了，则跳过
                if (supMapGp.get(xz_supKey) == -1) {
                    continue;
                }

                Set<Integer> y_neighbor = neighborNodeGp.get(y);
                // 如果z不是y的邻居
                if (y_neighbor == null || !y_neighbor.contains(z))
                    continue;

                String yz_supKey = Utils.getEdgeKey(y, z);
                // 若该边已经被删除了，则跳过
                if (supMapGp.get(yz_supKey) == -1) {
                    continue;
                }
                int xz_sup = supMapGp.get(xz_supKey);
                --xz_sup;
                int yz_sup = supMapGp.get(yz_supKey);
                --yz_sup;
                supMapGp.put(xz_supKey, xz_sup);
                supMapGp.put(yz_supKey, yz_sup);

                // 如果支持度小于k-2，则将其添加到Q中
                if (xz_sup < (k - 2)) {
                    tempQ.add(edgeIndexMapGp.get(xz_supKey));
                }
                if (yz_sup < (k - 2)) {
                    tempQ.add(edgeIndexMapGp.get(yz_supKey));
                }

            }

        }
    }


    /**
     * 创建Gp图
     *
     * @param path
     * @param targetNodeList
     */
    public void creatGpWithPStar(List<Integer> path, List<Node> targetNodeList) {
        // 元路径
        this.metaPath = path;
        edgeIndexMapGp = new HashMap<>();
        middleTypeNodePStar = new HashMap<>();

        // 标识边(x,y)是否已经存储
        Map<String, Boolean> edgeExist = new HashMap<>();

        // Gp图建边
        edgeListGp = new ArrayList<>();
        List<Node> tempX;
        List<Node> tempY;
        int l = metaPath.size();

        // 记录每个目标顶点的P/2-neighbor顶点
        Set<Integer> tempMiddleU;
        int middle = l / 2;

        for (Node node : targetNodeList) {
            tempX = new ArrayList<>();
            tempX.add(node);

            tempMiddleU = new HashSet<>();

            for (int i = 1; i < l; ++i) {
                tempY = new ArrayList<>();
                for (Node nodeX : tempX) {
                    for (int j = first[nodeX.getId()]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                        int v = adjacencyEdgeList.get(j).getV();
                        Node neighborNode = nodeList.get(v);
                        if (neighborNode.getType().equals(metaPath.get(i))) {
                            tempY.add(neighborNode);
                            // 记录目标顶点node的P/2-neighbor顶点
                            if (i == middle) {
                                tempMiddleU.add(v);
                            }
                        }
                    }
                }
                tempX = tempY;
            }

            // 将顶点node的P/2-neighbor顶点信息添加到对应的middleU中
            for (Integer middleU : tempMiddleU) {
                Set<Integer> pStar = middleTypeNodePStar.get(middleU);
                if (pStar == null) {
                    pStar = new HashSet<>();
                }
                pStar.add(node.getId());
                middleTypeNodePStar.put(middleU, pStar);
            }


            // 将找到的顶点与顶点v建边
            int u = node.getId();
            int x, y, v;
            for (Node nodeX : tempX) {
                v = nodeX.getId();
                // 跳过自环
                if (u == v) {
                    continue;
                }
                x = Math.min(u, v);
                y = u ^ v ^ x;
                String str = x + "-" + y;
                // 去除重边
                if (!edgeExist.containsKey(str)) {
                    edgeExist.put(str, true);
                    edgeListGp.add(new Edge(x, y, 0));
                }
            }
        }

        // 根据图G中的边来重新定义图Gp中的顶点和边
        reCreatNodeAndEdge(edgeListGp);

        firstGp = new int[nodeListGp.size() + 1];
        degreeGp = new int[nodeListGp.size() + 1];

        // 使用邻接表存储边
        // 同时计算每个顶点的度
        adjacencyEdgeListGp = Utils.addEdgeWithDegree(edgeListGp, nodeListGp.size(), firstGp, degreeGp);
    }

    /**
     * 创建Gp图
     *
     * @param path
     * @param targetNodeList
     */
    public void creatGp(List<Integer> path, List<Node> targetNodeList) {
        // 元路径
        this.metaPath = path;
        edgeIndexMapGp = new HashMap<>();

        // 标识边(x,y)是否已经存储
        Map<String, Boolean> edgeExist = new HashMap<>();

        // Gp图建边
        edgeListGp = new ArrayList<>();
        List<Node> tempX;
        List<Node> tempY;
        int l = metaPath.size();
        for (Node node : targetNodeList) {
            tempX = new ArrayList<>();
            tempX.add(node);
            for (int i = 1; i < l; ++i) {
                tempY = new ArrayList<>();
                for (Node nodeX : tempX) {
                    for (int j = first[nodeX.getId()]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                        int v = adjacencyEdgeList.get(j).getV();
                        Node neighborNode = nodeList.get(v);
                        if (neighborNode.getType().equals(metaPath.get(i))) {
                            tempY.add(neighborNode);
                        }
                    }
                }
                tempX = tempY;
            }
            // 将找到的顶点与顶点v建边
            int u = node.getId();
            int x, y, v;
            for (Node nodeX : tempX) {
                v = nodeX.getId();
                // 跳过自环
                if (u == v) {
                    continue;
                }
                x = Math.min(u, v);
                y = u ^ v ^ x;
                String str = x + "-" + y;
                // 去除重边
                if (!edgeExist.containsKey(str)) {
                    edgeExist.put(str, true);
                    edgeListGp.add(new Edge(x, y, 0));
                }
            }
        }

        // 根据图G中的边来重新定义图Gp中的顶点和边
        reCreatNodeAndEdge(edgeListGp);

        firstGp = new int[nodeListGp.size() + 1];
        degreeGp = new int[nodeListGp.size() + 1];

        // 使用邻接表存储边
        // 同时计算每个顶点的度
        adjacencyEdgeListGp = Utils.addEdgeWithDegree(edgeListGp, nodeListGp.size(), firstGp, degreeGp);
    }


    /**
     * 根据图G中的边来重新定义图Gp中的顶点和边
     *
     * @param edges
     */
    public void reCreatNodeAndEdge(List<Edge> edges) {
        // 顶点是否已经存入图中，存储G图到Gp图的索引映射
        GToGpMap = new HashMap<>();
        int u, v;
        nodeListGp = new ArrayList<>();
        neighborNodeGp = new HashMap<>();

        int index = 0;
        Node node;
        int x, y;
        for (int i = 0; i < edges.size(); ++i) {
            Edge edge = edges.get(i);
            u = edge.getU();
            v = edge.getV();
            if (!GToGpMap.containsKey(u)) {
                node = nodeList.get(u);
                x = index++;
                // 将在图G中的id改为在图Gp中的id
                node.setId(x);
                nodeListGp.add(node);
                GToGpMap.put(u, x);
            } else {
                x = GToGpMap.get(u);
            }
            if (!GToGpMap.containsKey(v)) {
                node = nodeList.get(v);
                y = index++;
                // 将在G图中的id改为在Gp图中的id
                node.setId(y);
                nodeListGp.add(node);
                GToGpMap.put(v, y);
            } else {
                y = GToGpMap.get(v);
            }
            // 重新将顶点id设置为在图Gp中的id
            edge.setU(x);
            edge.setV(y);
            // 存储每条边在edgeList中的索引
            edgeIndexMapGp.put(Utils.getEdgeKey(x, y), i);

            // 记录每个顶点的邻居顶点
            Set<Integer> x_neighbor = neighborNodeGp.get(x);
            if (x_neighbor == null) {
                x_neighbor = new HashSet<>();
            }
            x_neighbor.add(y);
            neighborNodeGp.put(x, x_neighbor);

            Set<Integer> y_neighbor = neighborNodeGp.get(y);
            if (y_neighbor == null) {
                y_neighbor = new HashSet<>();
            }
            y_neighbor.add(x);
            neighborNodeGp.put(y, y_neighbor);

        }

    }


    /**
     * 根据算法得到的edge结果来生成最终的图
     *
     * @param q
     */
    public void basicBTrussCommunitySearch(String q) {
        DisJointSet disJointSet = new DisJointSet(nodeListGp.size() + 1);

        boolean[] flag = new boolean[nodeListGp.size() + 1];
        for (Edge edge : edgeListGp) {
            int u = edge.getU();
            int v = edge.getV();
            String edgeKey = Utils.getEdgeKey(u, v);
            // 如果该边已经被删除了，则跳过
            if (supMapGp.get(edgeKey) == -1)
                continue;
            disJointSet.join(u, v);
            flag[u] = true;
            flag[v] = true;
            //System.out.println(edge);

        }
        int[] pre = new int[nodeListGp.size() + 1];

        int targetNodeIndex = -1;

        // 更新每个节点的祖先节点
        for (int i = 0; i < nodeListGp.size(); ++i) {
            pre[i] = disJointSet.find(i);
            // 寻找要查询的目标顶点在nodeListGp中的索引
            if (targetNodeIndex == -1) {
                if (q.equals(nodeListGp.get(i).getContent())) {
                    targetNodeIndex = i;
                }
            }
//            System.out.printf("pre[%d]=%d\n", i, pre[i]);
        }

        // 判断目标顶点是否存在于所生成的并查集中
        if (targetNodeIndex == -1) {
            System.out.println("未找到目标顶点q=" + q);
            return;
        } else {
            // 如果目标顶点没有在生成的并查集中，则说明不满足k-truss
            if (!flag[targetNodeIndex]) {
                System.out.println("未找到目标顶点q=" + q);
                return;
            }
        }

        System.out.println("找到的包含q的连通k-truss中的顶点如下：");
        int num = 0;
        for (int i = 0; i < nodeListGp.size(); ++i) {
            if (flag[i] && pre[i] == pre[targetNodeIndex]) {
                ++num;
                System.out.println(nodeListGp.get(i));
            }
        }
        System.out.println("共找到" + num + "个顶点");

    }


    private void computeSup(int[] first, int[] degree) {
        int x;
        int y;
        String edgeKey;
        supMap = new HashMap<>();
        for (Edge edge : edgeList) {// 对于边(x,y)
            // 小的顶点在前面，大的顶点在后面
            edgeKey = Utils.getEdgeKey(edge.getU(), edge.getV());
            // 去除重边的支持度的计算
            if (supMap.containsKey(edgeKey)) {
                continue;
            }
            // 令x为度较小的顶点
            if (degree[edge.getU()] <= degree[edge.getV()]) {
                x = edge.getU();
                y = edge.getV();
            } else {
                x = edge.getV();
                y = edge.getU();
            }
            int sup = 0;
            for (int i = first[x]; i != -1; i = adjacencyEdgeList.get(i).getNext()) {
                int z = adjacencyEdgeList.get(i).getV();// 得到边(x,z)
                for (int j = first[y]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                    if (adjacencyEdgeList.get(j).getV() == z) {// 若存在边(y,z),则边(x,y)的支持度加1
                        edge.increaseSup();
                        ++sup;
                    }
                }
            }
            supMap.put(edgeKey, sup);
        }
    }

    private void trussDecomposition() {
        int[] first = new int[nodeList.size() + 1];
        int[] degree = new int[nodeList.size() + 1];
        edgeTrussNess = new ArrayList<>();

        // 添加边
        Utils.addEdgeWithDegree(edgeList, nodeList.size(), first, degree);

        // 为每条边计算sup(e)
        computeSup(first, degree);

        int k = 2;
        int x;
        int y;
        while (!edgeList.isEmpty()) {
            // 对边按支持度进行升序排序
            Collections.sort(edgeList);

            Iterator<Edge> iterator = edgeList.iterator();
            int sup = k - 2;
            while (iterator.hasNext()) {
                Edge edge = iterator.next();
                String xy_supKey = Utils.getEdgeKey(edge.getU(), edge.getV());
                if (supMap.get(xy_supKey) <= sup) {
                    // 删除该边
                    edgeTrussNess.add(new Edge(edge.getU(), edge.getV(), edge.getSup(), k));
                    iterator.remove();
                    // 边(x,y)的支持度为-1表示该边已经被删除了
                    supMap.put(xy_supKey, -1);
                    --degree[edge.getU()];
                    --degree[edge.getV()];

                    // 令x为度较小的顶点
                    if (degree[edge.getU()] <= degree[edge.getV()]) {
                        x = edge.getU();
                        y = edge.getV();
                    } else {
                        x = edge.getV();
                        y = edge.getU();
                    }
                    // 更新在同一个三角形中其它边的sup
                    for (int i = first[x]; i != -1; i = adjacencyEdgeList.get(i).getNext()) {
                        int z = adjacencyEdgeList.get(i).getV();// 得到边(x,z)
                        String xz_supKey = Utils.getEdgeKey(x, z);
                        // 若该边已经被删除了，则跳过
                        if (supMap.get(xz_supKey) == -1) {
                            continue;
                        }
                        for (int j = first[y]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                            if (adjacencyEdgeList.get(j).getV() == z) {// 若存在边(y,z),则边(x,y)、(x,z)、(y,z)在一个三角形中
                                String yz_supKey = Utils.getEdgeKey(y, z);
                                // 若该边已经被删除了，则跳过
                                if (supMap.get(yz_supKey) == -1) {
                                    continue;
                                }
                                supMap.put(xz_supKey, supMap.get(xz_supKey) - 1);
                                supMap.put(yz_supKey, supMap.get(yz_supKey) - 1);
                            }
                        }
                    }
                }
            }
            ++k;
        }
    }


}
